Non-patent document 1 discloses a scheme for a key exchange device. A scheme which is realized by applying the scheme disclosed in Non-patent document 1 to a protocol (protocol3) disclosed in Non-patent document 2 will be described below with reference to FIG. 1.
FIG. 1 is a diagram showing a configurational example of key exchange device 200 according to the background art.
First, notations will be described below.
It is assumed that p represents a prime number and GT a cyclic group of order q. The number of key exchange devices 200 is represented by n and each of key exchange devices 200 is numbered with i. An identifier indicative of key exchange device 200(i) is represented by U[i]. g represents a generator of GT, v, w represent integral numbers that are selected at random. F, F′ represent pseudo-random number generating devices.
The configuration of key exchange device 200 will be described below.
As shown in FIG. 1, key exchange device 200 comprises verification data generator 208, temporal key generator 209, auxiliary data generator 216, contributing random number generator 219, contributing data generator 221, communicating section 223, and verification data verifier 226.
Key exchange device 200(i) thus constructed is supplied with partner identifier set 201 which is a set of identifiers of key exchange device 200(j) where j={1, . . . , n}¥i, and partner public key set 202(pid) which is a set of public keys pk[j] of key exchange device 200(j). Key exchange device 200(i) is also supplied with identifier 203(U[i]) and public key 204(pk[i]) of its own key exchange device 200(i) and private key 205(sk[i]) corresponding to public key 204(pk[i]). Key exchange device 200(i) is also supplied with session number 206(sid) unique to shared key 225(sk[i]) to be generated and random number 207.
In key exchange device 200(i), contributing random number generator 219 randomly generates contributing random number 200(r[i]εZ/qZ) using random number 207.
Then, in key exchange device 200(i), contributing data generator 221 generates contributing data 222(y[i]=gr[i]) using contributing random number 200(r[i]εZ/qZ) generated by contributing random number generator 219, and also generates signature sig(i,1) with respect to sid, 1, U[i], y[i].
Then, in key exchange device 200(i), communicating section 223 sends (sid, 1, U[i], y[i], sig(i,1)) to other (n−1) key exchange device 200(j).
In key exchange device 200(i), communicating section 223 waits for y(j) to be sent via communication link 224 from all key exchange devices 200(j) where j={1, . . . , n}¥i.
When all y[j] are supplied and contributing data set 218 is available, key exchange device 200(i) verifies each signature.
Then, in key exchange device 200(i), auxiliary data generator 216 generates auxiliary data 215(x[i]=(y[i+1]/y[i−1]r[i]) using contributing data set 218, and generates signature sig(i,2) with respect to (sid, 2, U[i], x[i]).
Then, in key exchange device 200(i), communicating section 223 sends (sid, 2, U[i], x[i], sig(i,2)) to other (n−1) key exchange device 200(j).
When all x[j] are supplied and auxiliary data set 212 is available, key exchange device 200(i) verifies each signature.
Then, in key exchange device 200(i), temporal key generator 209 generates k[i]=(y[i−1]r[i]nx[i+1]nx[i+2]n−1 . . . , x[n]i+1x[1]i . . . x[i−1]2 . . . x[1].
Then, in key exchange device 200(i), verification data generator 208 generates ack[i]=F(k[i],v), and temporal key generator 209 generates shared key 225 (sk[i]=F′(k[i],w)). Key exchange device 200(i) generates signature sig(i,3) with respect to (sid[i], 3, U[i], y[i], ack[i]).
Then, in key exchange device 200(i), communicating section 223 sends (sid, 3, U[i], ack[i], sig(i,3)) to other (n−1) key exchange device 200(j).
When all ack[j] are supplied, verification data verifier 226 of key exchange device 200(i) verifies each signature.
Thereafter, in key exchange device 200(i), verification data verifier 226 confirms ack[j]=ack[i] with respect to all j={1, . . . , n}¥i, and temporal key generator 209 outputs shared key 225 (sk[i]).
According to the background art shown in FIG. 1, however, each key exchange device has to be supplied with a unique session number. To this end, the key exchange devices which take part in a session need to distribute data such as random numbers to each other three times and to perform a process of joining the distributed data into a unique session number. Consequently, control cannot go to the next step unless the distribution to the entire system by all the key exchange devices is completed. The time required for the distribution is much longer than the time required to calculate each of the data. Therefore, for quickly exchanging keys between a number of key exchange devices, it is necessary to delete the distribution of such data.    Non-patent document 1: Jonathan Katz, Ji Sun Shin: Modeling insider attacks on group key-exchange protocols. ACM Conference on Computer and Communications Security 2005: 180-189    Non-patent document 2: Mike Burmester, Yvo Desmedt: A Secure and Efficient Conference Key Distribution System: 275-285